package com.jacky.dp;

public class 买卖股票的最佳时机III_123 {
    /*
     求最多买卖两次没交集（下一次买入前必须先卖出上一次的股票）的股票的最大利润，故在第下标 [0, i] 天买卖第一次，
     在第下标 [i, a.length) 天买卖第二次，这两次分别为前缀和后缀，即前后缀分解，前缀的最大利润+后缀的最大利润即为所求买卖两次的最大利润
     */
    public int maxProfit(int[] prices) {
        //获得数组长度
        int length = prices.length;
        //从左到右算最大利润
        int[] ltr = new int[length];
        //从右到左算最大利润
        int[] rtl = new int[length];

        //计算从左到右最大利润
        int leftMinPrice = prices[0];
        for (int i = 1; i < length; i++) {
            ltr[i] = Math.max(ltr[i - 1], prices[i] - leftMinPrice);
            leftMinPrice = Math.min(leftMinPrice, prices[i]);
        }
        //计算从右到左最大利润
        int rightMaxPrice = prices[length - 1];
        for (int i = length - 2; i >= 0; i--) {
            rtl[i] = Math.max(rightMaxPrice - prices[i], rtl[i + 1]);
            rightMaxPrice = Math.max(rightMaxPrice, prices[i]);
        }

        //这样就可把数组以某个元素切分为两段，ltr+rtl最大的时候，就是两次买卖可以获得的最大利润
        int res = 0;
        for (int k = 0; k < length; k++) {
            res = Math.max(ltr[k] + rtl[k], res);
        }
        return res;
    }
}
